<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">


<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    
    <title>pgmpy.inference.mplp &#8212; pgmpy 0.1.2 documentation</title>
    
    <link rel="stylesheet" href="../../../_static/sphinxdoc.css" type="text/css" />
    <link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
    
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    '../../../',
        VERSION:     '0.1.2',
        COLLAPSE_INDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  true,
        SOURCELINK_SUFFIX: '.txt'
      };
    </script>
    <script type="text/javascript" src="../../../_static/jquery.js"></script>
    <script type="text/javascript" src="../../../_static/underscore.js"></script>
    <script type="text/javascript" src="../../../_static/doctools.js"></script>
    <link rel="index" title="Index" href="../../../genindex.html" />
    <link rel="search" title="Search" href="../../../search.html" /> 
  </head>
  <body role="document">
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">pgmpy 0.1.2 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" accesskey="U">Module code</a> &#187;</li> 
      </ul>
    </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
            <p class="logo"><a href="../../../index.html">
              <img class="logo" src="../../../_static/logo.png" alt="Logo"/>
            </a></p>
<div id="searchbox" style="display: none" role="search">
  <h3>Quick search</h3>
    <form class="search" action="../../../search.html" method="get">
      <div><input type="text" name="q" /></div>
      <div><input type="submit" value="Go" /></div>
      <input type="hidden" name="check_keywords" value="yes" />
      <input type="hidden" name="area" value="default" />
    </form>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <h1>Source code for pgmpy.inference.mplp</h1><div class="highlight"><pre>
<span></span><span class="kn">from</span> <span class="nn">__future__</span> <span class="k">import</span> <span class="n">division</span>
<span class="kn">import</span> <span class="nn">copy</span>
<span class="kn">import</span> <span class="nn">itertools</span> <span class="k">as</span> <span class="nn">it</span>

<span class="kn">import</span> <span class="nn">numpy</span> <span class="k">as</span> <span class="nn">np</span>
<span class="kn">import</span> <span class="nn">networkx</span> <span class="k">as</span> <span class="nn">nx</span>

<span class="kn">from</span> <span class="nn">pgmpy.extern.six.moves</span> <span class="k">import</span> <span class="nb">filter</span><span class="p">,</span> <span class="nb">range</span>
<span class="kn">from</span> <span class="nn">pgmpy.inference</span> <span class="k">import</span> <span class="n">Inference</span>
<span class="kn">from</span> <span class="nn">pgmpy.models</span> <span class="k">import</span> <span class="n">MarkovModel</span>
<span class="kn">from</span> <span class="nn">pgmpy.factors.discrete</span> <span class="k">import</span> <span class="n">DiscreteFactor</span>


<div class="viewcode-block" id="Mplp"><a class="viewcode-back" href="../../../inference.html#pgmpy.inference.mplp.Mplp">[docs]</a><span class="k">class</span> <span class="nc">Mplp</span><span class="p">(</span><span class="n">Inference</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Class for performing approximate inference using Max-Product Linear Programming method.</span>

<span class="sd">    We derive message passing updates that result in monotone decrease of the dual of the</span>
<span class="sd">    MAP LP Relaxation.</span>

<span class="sd">    Parameters</span>
<span class="sd">    ----------</span>
<span class="sd">    model: MarkovModel for which inference is to be performed.</span>
<span class="sd">    Examples</span>
<span class="sd">    --------</span>
<span class="sd">    &gt;&gt;&gt; import numpy as np</span>
<span class="sd">    &gt;&gt;&gt; from pgmpy.models import MarkovModel</span>
<span class="sd">    &gt;&gt;&gt; from pgmpy.inference import Mplp</span>
<span class="sd">    &gt;&gt;&gt; from pgmpy.factors.discrete import DiscreteFactor</span>
<span class="sd">    &gt;&gt;&gt; student = MarkovModel()</span>
<span class="sd">    &gt;&gt;&gt; student.add_edges_from([(&#39;A&#39;, &#39;B&#39;), (&#39;B&#39;, &#39;C&#39;), (&#39;C&#39;, &#39;D&#39;), (&#39;E&#39;, &#39;F&#39;)])</span>
<span class="sd">    &gt;&gt;&gt; factor_a = DiscreteFactor([&#39;A&#39;], cardinality=[2], values=np.array([0.54577, 1.8323]))</span>
<span class="sd">    &gt;&gt;&gt; factor_b = DiscreteFactor([&#39;B&#39;], cardinality=[2], values=np.array([0.93894, 1.065]))</span>
<span class="sd">    &gt;&gt;&gt; factor_c = DiscreteFactor([&#39;C&#39;], cardinality=[2], values=np.array([0.89205, 1.121]))</span>
<span class="sd">    &gt;&gt;&gt; factor_d = DiscreteFactor([&#39;D&#39;], cardinality=[2], values=np.array([0.56292, 1.7765]))</span>
<span class="sd">    &gt;&gt;&gt; factor_e = DiscreteFactor([&#39;E&#39;], cardinality=[2], values=np.array([0.47117, 2.1224]))</span>
<span class="sd">    &gt;&gt;&gt; factor_f = DiscreteFactor([&#39;F&#39;], cardinality=[2], values=np.array([1.5093, 0.66257]))</span>
<span class="sd">    &gt;&gt;&gt; factor_a_b = DiscreteFactor([&#39;A&#39;, &#39;B&#39;], cardinality=[2, 2],</span>
<span class="sd">    ...                             values=np.array([1.3207, 0.75717, 0.75717, 1.3207]))</span>
<span class="sd">    &gt;&gt;&gt; factor_b_c = DiscreteFactor([&#39;B&#39;, &#39;C&#39;], cardinality=[2, 2],</span>
<span class="sd">    ...                             values=np.array([0.00024189, 4134.2, 4134.2, 0.00024189]))</span>
<span class="sd">    &gt;&gt;&gt; factor_c_d = DiscreteFactor([&#39;C&#39;, &#39;D&#39;], cardinality=[2, 2],</span>
<span class="sd">    ...                             values=np.array([0.0043227, 231.34, 231.34, 0.0043227]))</span>
<span class="sd">    &gt;&gt;&gt; factor_d_e = DiscreteFactor([&#39;E&#39;, &#39;F&#39;], cardinality=[2, 2],</span>
<span class="sd">    ...                             values=np.array([31.228, 0.032023, 0.032023, 31.228]))</span>
<span class="sd">    &gt;&gt;&gt; student.add_factors(factor_a, factor_b, factor_c, factor_d, factor_e, factor_f, factor_a_b,</span>
<span class="sd">    ...                     factor_b_c, factor_c_d, factor_d_e)</span>
<span class="sd">    &gt;&gt;&gt; mplp = Mplp(student)</span>
<span class="sd">    &quot;&quot;&quot;</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">model</span><span class="p">):</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">model</span><span class="p">,</span> <span class="n">MarkovModel</span><span class="p">):</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;Only MarkovModel is supported&#39;</span><span class="p">)</span>

        <span class="nb">super</span><span class="p">(</span><span class="n">Mplp</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__init__</span><span class="p">(</span><span class="n">model</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">model</span> <span class="o">=</span> <span class="n">model</span>

        <span class="c1"># S = \{c \cap c^{&#39;} : c, c^{&#39;} \in C, c \cap c^{&#39;} \neq \emptyset\}</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">intersection_set_variables</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
        <span class="c1"># We generate the Intersections of all the pairwise edges taken one at a time to form S</span>
        <span class="k">for</span> <span class="n">edge_pair</span> <span class="ow">in</span> <span class="n">it</span><span class="o">.</span><span class="n">combinations</span><span class="p">(</span><span class="n">model</span><span class="o">.</span><span class="n">edges</span><span class="p">(),</span> <span class="mi">2</span><span class="p">):</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">intersection_set_variables</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">edge_pair</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span> <span class="o">&amp;</span> <span class="nb">frozenset</span><span class="p">(</span><span class="n">edge_pair</span><span class="p">[</span><span class="mi">1</span><span class="p">]))</span>

        <span class="c1"># The corresponding optimization problem = \min_{\delta}{dual_lp(\delta)} where:</span>
        <span class="c1"># dual_lp(\delta) = \sum_{i \in V}{max_{x_i}(Objective[nodes])} + \sum_{f /in F}{max_{x_f}(Objective[factors])</span>
        <span class="c1"># Objective[nodes] = \theta_i(x_i) + \sum_{f \mid i \in f}{\delta_{fi}(x_i)}</span>
        <span class="c1"># Objective[factors] = \theta_f(x_f) - \sum_{i \in f}{\delta_{fi}(x_i)}</span>
        <span class="c1"># In a way Objective stores the corresponding optimization problem for all the nodes and the factors.</span>

        <span class="c1"># Form Objective and cluster_set in the form of a dictionary.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">objective</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">cluster_set</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="k">for</span> <span class="n">factor</span> <span class="ow">in</span> <span class="n">model</span><span class="o">.</span><span class="n">get_factors</span><span class="p">():</span>
            <span class="n">scope</span> <span class="o">=</span> <span class="nb">frozenset</span><span class="p">(</span><span class="n">factor</span><span class="o">.</span><span class="n">scope</span><span class="p">())</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="n">scope</span><span class="p">]</span> <span class="o">=</span> <span class="n">factor</span>
            <span class="c1"># For every factor consisting of more that a single node, we initialize a cluster.</span>
            <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">scope</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">cluster_set</span><span class="p">[</span><span class="n">scope</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">Cluster</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">intersection_set_variables</span><span class="p">,</span> <span class="n">factor</span><span class="p">)</span>

        <span class="c1"># dual_lp(\delta) is the dual linear program</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">dual_lp</span> <span class="o">=</span> <span class="nb">sum</span><span class="p">([</span><span class="n">np</span><span class="o">.</span><span class="n">amax</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="n">obj</span><span class="p">]</span><span class="o">.</span><span class="n">values</span><span class="p">)</span> <span class="k">for</span> <span class="n">obj</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">])</span>

        <span class="c1"># Best integral value of the primal objective is stored here</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">best_int_objective</span> <span class="o">=</span> <span class="mi">0</span>

        <span class="c1"># Assignment of the nodes that results in the &quot;maximum&quot; integral value of the primal objective</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">best_assignment</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="c1"># Results of the &quot;maximum&quot; integral value of the primal objective.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">best_decoded_result</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="c1"># This sets the minimum width between the dual objective decrements. Default value = 0.0002. This can be</span>
        <span class="c1"># changed in the map_query() method.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">dual_threshold</span> <span class="o">=</span> <span class="mf">0.0002</span>
        <span class="c1"># This sets the threshold for the integrality gap below which we say that the solution is satisfactory.</span>
        <span class="c1"># Default value = 0.0002. This can be changed in the map_query() method.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">integrality_gap_threshold</span> <span class="o">=</span> <span class="mf">0.0002</span>

<div class="viewcode-block" id="Mplp.Cluster"><a class="viewcode-back" href="../../../inference.html#pgmpy.inference.mplp.Mplp.Cluster">[docs]</a>    <span class="k">class</span> <span class="nc">Cluster</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Inner class for representing a cluster.</span>
<span class="sd">        A cluster is a subset of variables.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        set_of_variables: tuple</span>
<span class="sd">                          This is the set of variables that form the cluster.</span>

<span class="sd">        intersection_set_variables: set containing frozensets.</span>
<span class="sd">                                    collection of intersection of all pairs of cluster variables.</span>
<span class="sd">                        For eg: \{\{C_1 \cap C_2\}, \{C_2 \cap C_3\}, \{C_3 \cap C_1\} \} for clusters C_1, C_2 &amp; C_3.</span>

<span class="sd">        cluster_potential: DiscreteFactor</span>
<span class="sd">                           Each cluster has a initial probability distribution provided beforehand.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">intersection_set_variables</span><span class="p">,</span> <span class="n">cluster_potential</span><span class="p">):</span>
            <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">            Initialization of the current cluster</span>
<span class="sd">            &quot;&quot;&quot;</span>

            <span class="c1"># The variables with which the cluster is made of.</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">cluster_variables</span> <span class="o">=</span> <span class="nb">frozenset</span><span class="p">(</span><span class="n">cluster_potential</span><span class="o">.</span><span class="n">scope</span><span class="p">())</span>

            <span class="c1"># The cluster potentials must be specified before only.</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">cluster_potential</span> <span class="o">=</span> <span class="n">copy</span><span class="o">.</span><span class="n">deepcopy</span><span class="p">(</span><span class="n">cluster_potential</span><span class="p">)</span>

            <span class="c1"># Generate intersection sets for this cluster; S(c)</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">intersection_sets_for_cluster_c</span> <span class="o">=</span> <span class="p">[</span><span class="n">intersect</span><span class="o">.</span><span class="n">intersection</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">cluster_variables</span><span class="p">)</span>
                                                    <span class="k">for</span> <span class="n">intersect</span> <span class="ow">in</span> <span class="n">intersection_set_variables</span>
                                                    <span class="k">if</span> <span class="n">intersect</span><span class="o">.</span><span class="n">intersection</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">cluster_variables</span><span class="p">)]</span>

            <span class="c1"># Initialize messages from this cluster to its respective intersection sets</span>
            <span class="c1"># \lambda_{c \rightarrow \s} = 0</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">message_from_cluster</span> <span class="o">=</span> <span class="p">{}</span>
            <span class="k">for</span> <span class="n">intersection</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">intersection_sets_for_cluster_c</span><span class="p">:</span>
                <span class="c1"># Present variable. It can be a node or an edge too. (that is [&#39;A&#39;] or [&#39;A&#39;, &#39;C&#39;] too)</span>
                <span class="n">present_variables</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">intersection</span><span class="p">)</span>

                <span class="c1"># Present variables cardinality</span>
                <span class="n">present_variables_card</span> <span class="o">=</span> <span class="n">cluster_potential</span><span class="o">.</span><span class="n">get_cardinality</span><span class="p">(</span><span class="n">present_variables</span><span class="p">)</span>
                <span class="n">present_variables_card</span> <span class="o">=</span> <span class="p">[</span><span class="n">present_variables_card</span><span class="p">[</span><span class="n">var</span><span class="p">]</span> <span class="k">for</span> <span class="n">var</span> <span class="ow">in</span> <span class="n">present_variables</span><span class="p">]</span>

                <span class="c1"># We need to create a new factor whose messages are blank</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">message_from_cluster</span><span class="p">[</span><span class="n">intersection</span><span class="p">]</span> <span class="o">=</span> \
                    <span class="n">DiscreteFactor</span><span class="p">(</span><span class="n">present_variables</span><span class="p">,</span> <span class="n">present_variables_card</span><span class="p">,</span> <span class="n">np</span><span class="o">.</span><span class="n">zeros</span><span class="p">(</span><span class="n">np</span><span class="o">.</span><span class="n">prod</span><span class="p">(</span><span class="n">present_variables_card</span><span class="p">)))</span></div>

    <span class="k">def</span> <span class="nf">_update_message</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sending_cluster</span><span class="p">):</span>

        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        This is the message-update method.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        sending_cluster: The resulting messages are lambda_{c--&gt;s} from the given</span>
<span class="sd">            cluster &#39;c&#39; to all of its intersection_sets &#39;s&#39;.</span>
<span class="sd">            Here &#39;s&#39; are the elements of intersection_sets_for_cluster_c.</span>

<span class="sd">        Reference</span>
<span class="sd">        ---------</span>
<span class="sd">        Fixing Max-Product: Convergent Message-Passing Algorithms for MAP LP Relaxations</span>
<span class="sd">        by Amir Globerson and Tommi Jaakkola.</span>
<span class="sd">        Section 6, Page: 5; Beyond pairwise potentials: Generalized MPLP</span>
<span class="sd">        Later Modified by Sontag in &quot;Introduction to Dual decomposition for Inference&quot; Pg: 7 &amp; 17</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="c1"># The new updates will take place for the intersection_sets of this cluster.</span>
        <span class="c1"># The new updates are:</span>
        <span class="c1"># \delta_{f \rightarrow i}(x_i) = - \delta_i^{-f} +</span>
        <span class="c1"># 1/{\| f \|} max_{x_{f-i}}\left[{\theta_f(x_f) + \sum_{i&#39; in f}{\delta_{i&#39;}^{-f}}(x_i&#39;)} \right ]</span>

        <span class="c1"># Step. 1) Calculate {\theta_f(x_f) + \sum_{i&#39; in f}{\delta_{i&#39;}^{-f}}(x_i&#39;)}</span>
        <span class="n">objective_cluster</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="n">sending_cluster</span><span class="o">.</span><span class="n">cluster_variables</span><span class="p">]</span>
        <span class="k">for</span> <span class="n">current_intersect</span> <span class="ow">in</span> <span class="n">sending_cluster</span><span class="o">.</span><span class="n">intersection_sets_for_cluster_c</span><span class="p">:</span>
            <span class="n">objective_cluster</span> <span class="o">+=</span> <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="n">current_intersect</span><span class="p">]</span>

        <span class="n">updated_results</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="n">objective</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="k">for</span> <span class="n">current_intersect</span> <span class="ow">in</span> <span class="n">sending_cluster</span><span class="o">.</span><span class="n">intersection_sets_for_cluster_c</span><span class="p">:</span>
            <span class="c1"># Step. 2) Maximize step.1 result wrt variables present in the cluster but not in the current intersect.</span>
            <span class="n">phi</span> <span class="o">=</span> <span class="n">objective_cluster</span><span class="o">.</span><span class="n">maximize</span><span class="p">(</span><span class="nb">list</span><span class="p">(</span><span class="n">sending_cluster</span><span class="o">.</span><span class="n">cluster_variables</span> <span class="o">-</span> <span class="n">current_intersect</span><span class="p">),</span>
                                             <span class="n">inplace</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span>

            <span class="c1"># Step. 3) Multiply 1/{\| f \|}</span>
            <span class="n">intersection_length</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">sending_cluster</span><span class="o">.</span><span class="n">intersection_sets_for_cluster_c</span><span class="p">)</span>
            <span class="n">phi</span> <span class="o">*=</span> <span class="p">(</span><span class="mi">1</span> <span class="o">/</span> <span class="n">intersection_length</span><span class="p">)</span>
            <span class="n">objective</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">phi</span><span class="p">)</span>

            <span class="c1"># Step. 4) Subtract \delta_i^{-f}</span>
            <span class="c1"># These are the messages not emanating from the sending cluster but going into the current intersect.</span>
            <span class="c1"># which is = Objective[current_intersect_node] - messages from the cluster to the current intersect node.</span>
            <span class="n">updated_results</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">phi</span> <span class="o">+</span> <span class="o">-</span><span class="mi">1</span> <span class="o">*</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="n">current_intersect</span><span class="p">]</span> <span class="o">+</span> <span class="o">-</span><span class="mi">1</span> <span class="o">*</span> <span class="n">sending_cluster</span><span class="o">.</span>
                                               <span class="n">message_from_cluster</span><span class="p">[</span><span class="n">current_intersect</span><span class="p">]))</span>

        <span class="c1"># This loop is primarily for simultaneous updating:</span>
        <span class="c1"># 1. This cluster&#39;s message to each of the intersects.</span>
        <span class="c1"># 2. The value of the Objective for intersection_nodes.</span>
        <span class="n">index</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span>
        <span class="n">cluster_potential</span> <span class="o">=</span> <span class="n">copy</span><span class="o">.</span><span class="n">deepcopy</span><span class="p">(</span><span class="n">sending_cluster</span><span class="o">.</span><span class="n">cluster_potential</span><span class="p">)</span>
        <span class="k">for</span> <span class="n">current_intersect</span> <span class="ow">in</span> <span class="n">sending_cluster</span><span class="o">.</span><span class="n">intersection_sets_for_cluster_c</span><span class="p">:</span>
            <span class="n">index</span> <span class="o">+=</span> <span class="mi">1</span>
            <span class="n">sending_cluster</span><span class="o">.</span><span class="n">message_from_cluster</span><span class="p">[</span><span class="n">current_intersect</span><span class="p">]</span> <span class="o">=</span> <span class="n">updated_results</span><span class="p">[</span><span class="n">index</span><span class="p">]</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="n">current_intersect</span><span class="p">]</span> <span class="o">=</span> <span class="n">objective</span><span class="p">[</span><span class="n">index</span><span class="p">]</span>
            <span class="n">cluster_potential</span> <span class="o">+=</span> <span class="p">(</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="o">*</span> <span class="n">updated_results</span><span class="p">[</span><span class="n">index</span><span class="p">]</span>

        <span class="c1"># Here we update the Objective for the current factor.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="n">sending_cluster</span><span class="o">.</span><span class="n">cluster_variables</span><span class="p">]</span> <span class="o">=</span> <span class="n">cluster_potential</span>

    <span class="k">def</span> <span class="nf">_local_decode</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Finds the index of the maximum values for all the single node dual objectives.</span>

<span class="sd">        Reference:</span>
<span class="sd">        code presented by Sontag in 2012 here: http://cs.nyu.edu/~dsontag/code/README_v2.html</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c1"># The current assignment of the single node factors is stored in the form of a dictionary</span>
        <span class="n">decoded_result_assignment</span> <span class="o">=</span> <span class="p">{</span><span class="n">node</span><span class="p">:</span> <span class="n">np</span><span class="o">.</span><span class="n">argmax</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="n">node</span><span class="p">]</span><span class="o">.</span><span class="n">values</span><span class="p">)</span>
                                     <span class="k">for</span> <span class="n">node</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">objective</span> <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">node</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span><span class="p">}</span>
        <span class="c1"># Use the original cluster_potentials of each factor to find the primal integral value.</span>
        <span class="c1"># 1. For single node factors</span>
        <span class="n">integer_value</span> <span class="o">=</span> <span class="nb">sum</span><span class="p">([</span><span class="bp">self</span><span class="o">.</span><span class="n">factors</span><span class="p">[</span><span class="n">variable</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">values</span><span class="p">[</span><span class="n">decoded_result_assignment</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">([</span><span class="n">variable</span><span class="p">])]]</span>
                             <span class="k">for</span> <span class="n">variable</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">variables</span><span class="p">])</span>
        <span class="c1"># 2. For clusters</span>
        <span class="k">for</span> <span class="n">cluster_key</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">cluster_set</span><span class="p">:</span>
            <span class="n">cluster</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">cluster_set</span><span class="p">[</span><span class="n">cluster_key</span><span class="p">]</span>
            <span class="n">index</span> <span class="o">=</span> <span class="p">[</span><span class="nb">tuple</span><span class="p">([</span><span class="n">variable</span><span class="p">,</span> <span class="n">decoded_result_assignment</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">([</span><span class="n">variable</span><span class="p">])]])</span>
                     <span class="k">for</span> <span class="n">variable</span> <span class="ow">in</span> <span class="n">cluster</span><span class="o">.</span><span class="n">cluster_variables</span><span class="p">]</span>
            <span class="n">integer_value</span> <span class="o">+=</span> <span class="n">cluster</span><span class="o">.</span><span class="n">cluster_potential</span><span class="o">.</span><span class="n">reduce</span><span class="p">(</span><span class="n">index</span><span class="p">,</span> <span class="n">inplace</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span><span class="o">.</span><span class="n">values</span>

        <span class="c1"># Check if this is the best assignment till now</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">best_int_objective</span> <span class="o">&lt;</span> <span class="n">integer_value</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">best_int_objective</span> <span class="o">=</span> <span class="n">integer_value</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">best_assignment</span> <span class="o">=</span> <span class="n">decoded_result_assignment</span>

    <span class="k">def</span> <span class="nf">_is_converged</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">dual_threshold</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">integrality_gap_threshold</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        This method checks the integrality gap to ensure either:</span>
<span class="sd">            * we have found a near to exact solution or</span>
<span class="sd">            * stuck on a local minima.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        dual_threshold: double</span>
<span class="sd">                        This sets the minimum width between the dual objective decrements. If the decrement is lesser</span>
<span class="sd">                        than the threshold, then that means we have stuck on a local minima.</span>

<span class="sd">        integrality_gap_threshold: double</span>
<span class="sd">                                   This sets the threshold for the integrality gap below which we say that the solution</span>
<span class="sd">                                   is satisfactory.</span>

<span class="sd">        References</span>
<span class="sd">        ----------</span>
<span class="sd">        code presented by Sontag in 2012 here: http://cs.nyu.edu/~dsontag/code/README_v2.html</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c1"># Find the new objective after the message updates</span>
        <span class="n">new_dual_lp</span> <span class="o">=</span> <span class="nb">sum</span><span class="p">([</span><span class="n">np</span><span class="o">.</span><span class="n">amax</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="n">obj</span><span class="p">]</span><span class="o">.</span><span class="n">values</span><span class="p">)</span> <span class="k">for</span> <span class="n">obj</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">])</span>

        <span class="c1"># Update the dual_gap as the difference between the dual objective of the previous and the current iteration.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">dual_gap</span> <span class="o">=</span> <span class="nb">abs</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">dual_lp</span> <span class="o">-</span> <span class="n">new_dual_lp</span><span class="p">)</span>

        <span class="c1"># Update the integrality_gap as the difference between our best result vs the dual objective of the lp.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">integrality_gap</span> <span class="o">=</span> <span class="nb">abs</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">dual_lp</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">best_int_objective</span><span class="p">)</span>

        <span class="c1"># As the decrement of the dual_lp gets very low, we assume that we might have stuck in a local minima.</span>
        <span class="k">if</span> <span class="n">dual_threshold</span> <span class="ow">and</span> <span class="bp">self</span><span class="o">.</span><span class="n">dual_gap</span> <span class="o">&lt;</span> <span class="n">dual_threshold</span><span class="p">:</span>
            <span class="k">return</span> <span class="kc">True</span>
        <span class="c1"># Check the threshold for the integrality gap</span>
        <span class="k">elif</span> <span class="n">integrality_gap_threshold</span> <span class="ow">and</span> <span class="bp">self</span><span class="o">.</span><span class="n">integrality_gap</span> <span class="o">&lt;</span> <span class="n">integrality_gap_threshold</span><span class="p">:</span>
            <span class="k">return</span> <span class="kc">True</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">dual_lp</span> <span class="o">=</span> <span class="n">new_dual_lp</span>
            <span class="k">return</span> <span class="kc">False</span>

<div class="viewcode-block" id="Mplp.find_triangles"><a class="viewcode-back" href="../../../inference.html#pgmpy.inference.mplp.Mplp.find_triangles">[docs]</a>    <span class="k">def</span> <span class="nf">find_triangles</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Finds all the triangles present in the given model</span>

<span class="sd">        Examples</span>
<span class="sd">        --------</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.models import MarkovModel</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.factors.discrete import DiscreteFactor</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.inference import Mplp</span>
<span class="sd">        &gt;&gt;&gt; mm = MarkovModel()</span>
<span class="sd">        &gt;&gt;&gt; mm.add_nodes_from([&#39;x1&#39;, &#39;x2&#39;, &#39;x3&#39;, &#39;x4&#39;, &#39;x5&#39;, &#39;x6&#39;, &#39;x7&#39;])</span>
<span class="sd">        &gt;&gt;&gt; mm.add_edges_from([(&#39;x1&#39;, &#39;x3&#39;), (&#39;x1&#39;, &#39;x4&#39;), (&#39;x2&#39;, &#39;x4&#39;),</span>
<span class="sd">        ...                    (&#39;x2&#39;, &#39;x5&#39;), (&#39;x3&#39;, &#39;x6&#39;), (&#39;x4&#39;, &#39;x6&#39;),</span>
<span class="sd">        ...                    (&#39;x4&#39;, &#39;x7&#39;), (&#39;x5&#39;, &#39;x7&#39;)])</span>
<span class="sd">        &gt;&gt;&gt; phi = [DiscreteFactor(edge, [2, 2], np.random.rand(4)) for edge in mm.edges()]</span>
<span class="sd">        &gt;&gt;&gt; mm.add_factors(*phi)</span>
<span class="sd">        &gt;&gt;&gt; mplp = Mplp(mm)</span>
<span class="sd">        &gt;&gt;&gt; mplp.find_triangles()</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="nb">filter</span><span class="p">(</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="nb">len</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">==</span> <span class="mi">3</span><span class="p">,</span> <span class="n">nx</span><span class="o">.</span><span class="n">find_cliques</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">model</span><span class="p">)))</span></div>

    <span class="k">def</span> <span class="nf">_update_triangles</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">triangles_list</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        From a set of variables forming a triangle in the model, we form the corresponding Clusters.</span>
<span class="sd">        These clusters are then appended to the code.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        triangle_list : list</span>
<span class="sd">                        The list of variables forming the triangles to be updated. It is of the form of</span>
<span class="sd">                        [[&#39;var_5&#39;, &#39;var_8&#39;, &#39;var_7&#39;], [&#39;var_4&#39;, &#39;var_5&#39;, &#39;var_7&#39;]]</span>

<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">new_intersection_set</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="k">for</span> <span class="n">triangle_vars</span> <span class="ow">in</span> <span class="n">triangles_list</span><span class="p">:</span>
            <span class="n">cardinalities</span> <span class="o">=</span> <span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">cardinality</span><span class="p">[</span><span class="n">variable</span><span class="p">]</span> <span class="k">for</span> <span class="n">variable</span> <span class="ow">in</span> <span class="n">triangle_vars</span><span class="p">]</span>
            <span class="n">current_intersection_set</span> <span class="o">=</span> <span class="p">[</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">intersect</span><span class="p">)</span> <span class="k">for</span> <span class="n">intersect</span> <span class="ow">in</span> <span class="n">it</span><span class="o">.</span><span class="n">combinations</span><span class="p">(</span><span class="n">triangle_vars</span><span class="p">,</span> <span class="mi">2</span><span class="p">)]</span>
            <span class="n">current_factor</span> <span class="o">=</span> <span class="n">DiscreteFactor</span><span class="p">(</span><span class="n">triangle_vars</span><span class="p">,</span> <span class="n">cardinalities</span><span class="p">,</span> <span class="n">np</span><span class="o">.</span><span class="n">zeros</span><span class="p">(</span><span class="n">np</span><span class="o">.</span><span class="n">prod</span><span class="p">(</span><span class="n">cardinalities</span><span class="p">)))</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">cluster_set</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">triangle_vars</span><span class="p">)]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">Cluster</span><span class="p">(</span><span class="n">current_intersection_set</span><span class="p">,</span> <span class="n">current_factor</span><span class="p">)</span>
            <span class="c1"># add new factors</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">model</span><span class="o">.</span><span class="n">factors</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">current_factor</span><span class="p">)</span>
            <span class="c1"># add new intersection sets</span>
            <span class="n">new_intersection_set</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">current_intersection_set</span><span class="p">)</span>
            <span class="c1"># add new factors in objective</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">triangle_vars</span><span class="p">)]</span> <span class="o">=</span> <span class="n">current_factor</span>

    <span class="k">def</span> <span class="nf">_get_triplet_scores</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">triangles_list</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns the score of each of the triplets found in the current model</span>

<span class="sd">        Parameters</span>
<span class="sd">        ---------</span>
<span class="sd">        triangles_list: list</span>
<span class="sd">                        The list of variables forming the triangles to be updated. It is of the form of</span>
<span class="sd">                        [[&#39;var_5&#39;, &#39;var_8&#39;, &#39;var_7&#39;], [&#39;var_4&#39;, &#39;var_5&#39;, &#39;var_7&#39;]]</span>

<span class="sd">        Return: {frozenset({&#39;var_8&#39;, &#39;var_5&#39;, &#39;var_7&#39;}): 5.024, frozenset({&#39;var_5&#39;, &#39;var_4&#39;, &#39;var_7&#39;}): 10.23}</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">triplet_scores</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="k">for</span> <span class="n">triplet</span> <span class="ow">in</span> <span class="n">triangles_list</span><span class="p">:</span>

            <span class="c1"># Find the intersection sets of the current triplet</span>
            <span class="n">triplet_intersections</span> <span class="o">=</span> <span class="p">[</span><span class="n">intersect</span> <span class="k">for</span> <span class="n">intersect</span> <span class="ow">in</span> <span class="n">it</span><span class="o">.</span><span class="n">combinations</span><span class="p">(</span><span class="n">triplet</span><span class="p">,</span> <span class="mi">2</span><span class="p">)]</span>

            <span class="c1"># Independent maximization</span>
            <span class="n">ind_max</span> <span class="o">=</span> <span class="nb">sum</span><span class="p">([</span><span class="n">np</span><span class="o">.</span><span class="n">amax</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">intersect</span><span class="p">)]</span><span class="o">.</span><span class="n">values</span><span class="p">)</span> <span class="k">for</span> <span class="n">intersect</span> <span class="ow">in</span> <span class="n">triplet_intersections</span><span class="p">])</span>

            <span class="c1"># Joint maximization</span>
            <span class="n">joint_max</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">triplet_intersections</span><span class="p">[</span><span class="mi">0</span><span class="p">])]</span>
            <span class="k">for</span> <span class="n">intersect</span> <span class="ow">in</span> <span class="n">triplet_intersections</span><span class="p">[</span><span class="mi">1</span><span class="p">:]:</span>
                <span class="n">joint_max</span> <span class="o">+=</span> <span class="bp">self</span><span class="o">.</span><span class="n">objective</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">intersect</span><span class="p">)]</span>
            <span class="n">joint_max</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">amax</span><span class="p">(</span><span class="n">joint_max</span><span class="o">.</span><span class="n">values</span><span class="p">)</span>
            <span class="c1"># score = Independent maximization solution - Joint maximization solution</span>
            <span class="n">score</span> <span class="o">=</span> <span class="n">ind_max</span> <span class="o">-</span> <span class="n">joint_max</span>
            <span class="n">triplet_scores</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">triplet</span><span class="p">)]</span> <span class="o">=</span> <span class="n">score</span>

        <span class="k">return</span> <span class="n">triplet_scores</span>

    <span class="k">def</span> <span class="nf">_run_mplp</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">no_iterations</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Updates messages until either Mplp converges or if doesn&#39;t converges; halts after no_iterations.</span>

<span class="sd">        Parameters</span>
<span class="sd">        --------</span>
<span class="sd">        no_iterations:  integer</span>
<span class="sd">                        Number of maximum iterations that we want MPLP to run.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">for</span> <span class="n">niter</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">no_iterations</span><span class="p">):</span>
            <span class="c1"># We take the clusters in the order they were added in the model and update messages for all factors whose</span>
            <span class="c1"># scope is greater than 1</span>
            <span class="k">for</span> <span class="n">factor</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">model</span><span class="o">.</span><span class="n">get_factors</span><span class="p">():</span>
                <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">factor</span><span class="o">.</span><span class="n">scope</span><span class="p">())</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
                    <span class="bp">self</span><span class="o">.</span><span class="n">_update_message</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">cluster_set</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">factor</span><span class="o">.</span><span class="n">scope</span><span class="p">())])</span>
            <span class="c1"># Find an integral solution by locally maximizing the single node beliefs</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_local_decode</span><span class="p">()</span>
            <span class="c1"># If mplp converges to a global/local optima, we break.</span>
            <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_is_converged</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">dual_threshold</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">integrality_gap_threshold</span><span class="p">)</span> <span class="ow">and</span> <span class="n">niter</span> <span class="o">&gt;=</span> <span class="mi">16</span><span class="p">:</span>
                <span class="k">break</span>

    <span class="k">def</span> <span class="nf">_tighten_triplet</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">max_iterations</span><span class="p">,</span> <span class="n">later_iter</span><span class="p">,</span> <span class="n">max_triplets</span><span class="p">,</span> <span class="n">prolong</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        This method finds all the triplets that are eligible and adds them iteratively in the bunch of max_triplets</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        max_iterations: integer</span>
<span class="sd">                        Maximum number of times we tighten the relaxation</span>

<span class="sd">        later_iter: integer</span>
<span class="sd">                    Number of maximum iterations that we want MPLP to run. This is lesser than the initial number</span>
<span class="sd">                    of iterations.</span>

<span class="sd">        max_triplets: integer</span>
<span class="sd">                      Maximum number of triplets that can be added atmost in one iteration.</span>

<span class="sd">        prolong: bool</span>
<span class="sd">                It sets the continuation of tightening after all the triplets are exhausted</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c1"># Find all the triplets that are possible in the present model</span>
        <span class="n">triangles</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">find_triangles</span><span class="p">()</span>
        <span class="c1"># Evaluate scores for each of the triplets found above</span>
        <span class="n">triplet_scores</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_get_triplet_scores</span><span class="p">(</span><span class="n">triangles</span><span class="p">)</span>
        <span class="c1"># Arrange the keys on the basis of increasing order of the values of the dict. triplet_scores</span>
        <span class="n">sorted_scores</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="n">triplet_scores</span><span class="p">,</span> <span class="n">key</span><span class="o">=</span><span class="n">triplet_scores</span><span class="o">.</span><span class="n">get</span><span class="p">)</span>
        <span class="k">for</span> <span class="n">niter</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">max_iterations</span><span class="p">):</span>
            <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_is_converged</span><span class="p">(</span><span class="n">integrality_gap_threshold</span><span class="o">=</span><span class="bp">self</span><span class="o">.</span><span class="n">integrality_gap_threshold</span><span class="p">):</span>
                <span class="k">break</span>
            <span class="c1"># add triplets that are yet not added.</span>
            <span class="n">add_triplets</span> <span class="o">=</span> <span class="p">[]</span>
            <span class="k">for</span> <span class="n">triplet_number</span> <span class="ow">in</span> <span class="p">(</span><span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">sorted_scores</span><span class="p">))):</span>
                <span class="c1"># At once, we can add atmost 5 triplets</span>
                <span class="k">if</span> <span class="n">triplet_number</span> <span class="o">&gt;=</span> <span class="n">max_triplets</span><span class="p">:</span>
                    <span class="k">break</span>
                <span class="n">add_triplets</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">sorted_scores</span><span class="o">.</span><span class="n">pop</span><span class="p">())</span>
            <span class="c1"># Break from the tighten triplets loop if there are no triplets to add if the prolong is set to False</span>
            <span class="k">if</span> <span class="ow">not</span> <span class="n">add_triplets</span> <span class="ow">and</span> <span class="n">prolong</span> <span class="ow">is</span> <span class="kc">False</span><span class="p">:</span>
                    <span class="k">break</span>
            <span class="c1"># Update the eligible triplets to tighten the relaxation</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_update_triangles</span><span class="p">(</span><span class="n">add_triplets</span><span class="p">)</span>
            <span class="c1"># Run MPLP for a maximum of later_iter times.</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_run_mplp</span><span class="p">(</span><span class="n">later_iter</span><span class="p">)</span>

<div class="viewcode-block" id="Mplp.get_integrality_gap"><a class="viewcode-back" href="../../../inference.html#pgmpy.inference.mplp.Mplp.get_integrality_gap">[docs]</a>    <span class="k">def</span> <span class="nf">get_integrality_gap</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns the integrality gap of the current state of the Mplp algorithm. The lesser it is, the closer we are</span>
<span class="sd">                towards the exact solution.</span>

<span class="sd">        Example:</span>
<span class="sd">        --------</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.models import MarkovModel</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.factors.discrete import DiscreteFactor</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.inference import Mplp</span>
<span class="sd">        &gt;&gt;&gt; mm = MarkovModel()</span>
<span class="sd">        &gt;&gt;&gt; mm.add_nodes_from([&#39;x1&#39;, &#39;x2&#39;, &#39;x3&#39;, &#39;x4&#39;, &#39;x5&#39;, &#39;x6&#39;, &#39;x7&#39;])</span>
<span class="sd">        &gt;&gt;&gt; mm.add_edges_from([(&#39;x1&#39;, &#39;x3&#39;), (&#39;x1&#39;, &#39;x4&#39;), (&#39;x2&#39;, &#39;x4&#39;),</span>
<span class="sd">        ...                    (&#39;x2&#39;, &#39;x5&#39;), (&#39;x3&#39;, &#39;x6&#39;), (&#39;x4&#39;, &#39;x6&#39;),</span>
<span class="sd">        ...                    (&#39;x4&#39;, &#39;x7&#39;), (&#39;x5&#39;, &#39;x7&#39;)])</span>
<span class="sd">        &gt;&gt;&gt; phi = [DiscreteFactor(edge, [2, 2], np.random.rand(4)) for edge in mm.edges()]</span>
<span class="sd">        &gt;&gt;&gt; mm.add_factors(*phi)</span>
<span class="sd">        &gt;&gt;&gt; mplp = Mplp(mm)</span>
<span class="sd">        &gt;&gt;&gt; mplp.map_query()</span>
<span class="sd">        &gt;&gt;&gt; int_gap = mplp.get_integrality_gap()</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">integrality_gap</span></div>

    <span class="k">def</span> <span class="nf">query</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">raise</span> <span class="ne">NotImplementedError</span><span class="p">(</span><span class="s2">&quot;map_query() is the only query method available.&quot;</span><span class="p">)</span>

<div class="viewcode-block" id="Mplp.map_query"><a class="viewcode-back" href="../../../inference.html#pgmpy.inference.mplp.Mplp.map_query">[docs]</a>    <span class="k">def</span> <span class="nf">map_query</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">init_iter</span><span class="o">=</span><span class="mi">1000</span><span class="p">,</span> <span class="n">later_iter</span><span class="o">=</span><span class="mi">20</span><span class="p">,</span> <span class="n">dual_threshold</span><span class="o">=</span><span class="mf">0.0002</span><span class="p">,</span> <span class="n">integrality_gap_threshold</span><span class="o">=</span><span class="mf">0.0002</span><span class="p">,</span>
                  <span class="n">tighten_triplet</span><span class="o">=</span><span class="kc">True</span><span class="p">,</span> <span class="n">max_triplets</span><span class="o">=</span><span class="mi">5</span><span class="p">,</span> <span class="n">max_iterations</span><span class="o">=</span><span class="mi">100</span><span class="p">,</span> <span class="n">prolong</span><span class="o">=</span><span class="kc">False</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        MAP query method using Max Product LP method.</span>
<span class="sd">        This returns the best assignment of the nodes in the form of a dictionary.</span>

<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        init_iter: integer</span>
<span class="sd">                   Number of maximum iterations that we want MPLP to run for the first time.</span>

<span class="sd">        later_iter: integer</span>
<span class="sd">                    Number of maximum iterations that we want MPLP to run for later iterations</span>

<span class="sd">        dual_threshold: double</span>
<span class="sd">                        This sets the minimum width between the dual objective decrements. If the decrement is lesser</span>
<span class="sd">                        than the threshold, then that means we have stuck on a local minima.</span>

<span class="sd">        integrality_gap_threshold: double</span>
<span class="sd">                                   This sets the threshold for the integrality gap below which we say that the solution</span>
<span class="sd">                                   is satisfactory.</span>

<span class="sd">        tighten_triplet: bool</span>
<span class="sd">                         set whether to use triplets as clusters or not.</span>

<span class="sd">        max_triplets: integer</span>
<span class="sd">                      Set the maximum number of triplets that can be added at once.</span>

<span class="sd">        max_iterations: integer</span>
<span class="sd">                        Maximum number of times we tighten the relaxation. Used only when tighten_triplet is set True.</span>

<span class="sd">        prolong: bool</span>
<span class="sd">                 If set False: The moment we exhaust of all the triplets the tightening stops.</span>
<span class="sd">                 If set True: The tightening will be performed max_iterations number of times irrespective of the</span>
<span class="sd">                              triplets.</span>

<span class="sd">        Reference:</span>
<span class="sd">        Section 3.3: The Dual Algorithm; Tightening LP Relaxation for MAP using Message Passing (2008)</span>
<span class="sd">        By Sontag Et al.</span>

<span class="sd">        Examples</span>
<span class="sd">        --------</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.models import MarkovModel</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.factors.discrete import DiscreteFactor</span>
<span class="sd">        &gt;&gt;&gt; from pgmpy.inference import Mplp</span>
<span class="sd">        &gt;&gt;&gt; import numpy as np</span>
<span class="sd">        &gt;&gt;&gt; student = MarkovModel()</span>
<span class="sd">        &gt;&gt;&gt; student.add_edges_from([(&#39;A&#39;, &#39;B&#39;), (&#39;B&#39;, &#39;C&#39;), (&#39;C&#39;, &#39;D&#39;), (&#39;E&#39;, &#39;F&#39;)])</span>
<span class="sd">        &gt;&gt;&gt; factor_a = DiscreteFactor([&#39;A&#39;], cardinality=[2], values=np.array([0.54577, 1.8323]))</span>
<span class="sd">        &gt;&gt;&gt; factor_b = DiscreteFactor([&#39;B&#39;], cardinality=[2], values=np.array([0.93894, 1.065]))</span>
<span class="sd">        &gt;&gt;&gt; factor_c = DiscreteFactor([&#39;C&#39;], cardinality=[2], values=np.array([0.89205, 1.121]))</span>
<span class="sd">        &gt;&gt;&gt; factor_d = DiscreteFactor([&#39;D&#39;], cardinality=[2], values=np.array([0.56292, 1.7765]))</span>
<span class="sd">        &gt;&gt;&gt; factor_e = DiscreteFactor([&#39;E&#39;], cardinality=[2], values=np.array([0.47117, 2.1224]))</span>
<span class="sd">        &gt;&gt;&gt; factor_f = DiscreteFactor([&#39;F&#39;], cardinality=[2], values=np.array([1.5093, 0.66257]))</span>
<span class="sd">        &gt;&gt;&gt; factor_a_b = DiscreteFactor([&#39;A&#39;, &#39;B&#39;], cardinality=[2, 2],</span>
<span class="sd">        ...                             values=np.array([1.3207, 0.75717, 0.75717, 1.3207]))</span>
<span class="sd">        &gt;&gt;&gt; factor_b_c = DiscreteFactor([&#39;B&#39;, &#39;C&#39;], cardinality=[2, 2],</span>
<span class="sd">        ...                             values=np.array([0.00024189, 4134.2, 4134.2, 0.0002418]))</span>
<span class="sd">        &gt;&gt;&gt; factor_c_d = DiscreteFactor([&#39;C&#39;, &#39;D&#39;], cardinality=[2, 2],</span>
<span class="sd">        ...                             values=np.array([0.0043227, 231.34, 231.34, 0.0043227]))</span>
<span class="sd">        &gt;&gt;&gt; factor_d_e = DiscreteFactor([&#39;E&#39;, &#39;F&#39;], cardinality=[2, 2],</span>
<span class="sd">        ...                             values=np.array([31.228, 0.032023, 0.032023, 31.228]))</span>
<span class="sd">        &gt;&gt;&gt; student.add_factors(factor_a, factor_b, factor_c, factor_d, factor_e, factor_f,</span>
<span class="sd">        ...                     factor_a_b, factor_b_c, factor_c_d, factor_d_e)</span>
<span class="sd">        &gt;&gt;&gt; mplp = Mplp(student)</span>
<span class="sd">        &gt;&gt;&gt; result = mplp.map_query()</span>
<span class="sd">        &gt;&gt;&gt; result</span>
<span class="sd">        {&#39;B&#39;: 0.93894, &#39;C&#39;: 1.121, &#39;A&#39;: 1.8323, &#39;F&#39;: 1.5093, &#39;D&#39;: 1.7765, &#39;E&#39;: 2.12239}</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="bp">self</span><span class="o">.</span><span class="n">dual_threshold</span> <span class="o">=</span> <span class="n">dual_threshold</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">integrality_gap_threshold</span> <span class="o">=</span> <span class="n">integrality_gap_threshold</span>
        <span class="c1"># Run MPLP initially for a maximum of init_iter times.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_run_mplp</span><span class="p">(</span><span class="n">init_iter</span><span class="p">)</span>
        <span class="c1"># If triplets are to be used for the tightening, we proceed as follows</span>
        <span class="k">if</span> <span class="n">tighten_triplet</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_tighten_triplet</span><span class="p">(</span><span class="n">max_iterations</span><span class="p">,</span> <span class="n">later_iter</span><span class="p">,</span> <span class="n">max_triplets</span><span class="p">,</span> <span class="n">prolong</span><span class="p">)</span>
        <span class="c1"># Get the best result from the best assignment</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">best_decoded_result</span> <span class="o">=</span> <span class="p">{</span><span class="n">factor</span><span class="o">.</span><span class="n">scope</span><span class="p">()[</span><span class="mi">0</span><span class="p">]:</span> <span class="n">factor</span><span class="o">.</span><span class="n">values</span><span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">best_assignment</span><span class="p">[</span><span class="nb">frozenset</span><span class="p">(</span><span class="n">factor</span><span class="o">.</span><span class="n">scope</span><span class="p">())]]</span>
                                    <span class="k">for</span> <span class="n">factor</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">model</span><span class="o">.</span><span class="n">factors</span> <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">factor</span><span class="o">.</span><span class="n">scope</span><span class="p">())</span> <span class="o">==</span> <span class="mi">1</span><span class="p">}</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">best_decoded_result</span></div></div>
</pre></div>

          </div>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">pgmpy 0.1.2 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" >Module code</a> &#187;</li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2016, Ankur Ankan.
      Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.5.1.
    </div>
  </body>
</html>